package test;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class TengXun5 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        int num = scanner.nextInt();
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < num; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            if (start < 0){
                start = 0;
            }
            if (end > str.length()){
                end = str.length();
            }
            String temp = str.substring(start - 1,end);
            if (map.containsKey(temp)){
                System.out.println(map.get(temp));
            }else {
                int res = getRes(temp);
                System.out.println(res);
                map.put(temp,res);
            }

        }
    }

    private static int getRes(String str) {
        int length = str.length();
        if (length < 2){
            return 0;
        }
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = i;
        }
        boolean[][] check = new boolean[length][length];
        for (int right = 0; right < length; right++) {
            for (int left = 0; left <= right; left++) {
                if (str.charAt(left) == str.charAt(right) && (right - left <= 2 || check[left + 1][right - 1])){
                    check[left][right] = true;
                }
            }
        }
        for (int i = 1; i < length; i++) {
            if (check[0][i]){
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (check[j + 1][i]){
                    dp[i] = Math.min(dp[i],dp[j] + 1);
                }
            }
        }
        return dp[length - 1] + 1;
    }
}
